#include <string.h>
#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
    return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
    return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
    return numEntries;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
    // if full, err out
    if (numEntries == maxEntries) {
        return RC_NODE_FULL;
    }
    // find the correct spot and make a gap.
    int i = 0;
    while(i < numEntries) {
        if(rKPs[i].key >= key){
            memmove(rKPs + i + 1 , rKPs + i, sizeRKP * (numEntries - i));
            break;
        }
        i++;
    }
    
    // add rKP
    rKPs[i] = rKP(rid, key);
    
    //increment count
    numEntries++;
    
    return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
    if (numEntries < 1){
        return RC_TOO_FEW_FOR_INSERT_AND_SPLIT;
    }


    const int split = numEntries / 2;
    
    // determine where new node will be inserted
    if(rKPs[split].key <= key){
        sibling.numEntries = numEntries - (split + 1);
        numEntries = split + 1;
        memcpy(sibling.rKPs, rKPs + split + 1, sizeRKP * sibling.numEntries);
        sibling.insert(key, rid);
    }
    else{
        sibling.numEntries = numEntries - split;
        numEntries = split;
        memcpy(sibling.rKPs, rKPs + split, sizeRKP * sibling.numEntries);
        insert(key, rid);
    }
    
    siblingKey = sibling.rKPs[0].key;
    
    return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
    for (int i = 0; i < maxEntries; i++) {
        if( rKPs[i].key >= searchKey) {
            eid = i;
            return 0;
        }
    }
    
    return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
    rid = rKPs[eid].record;
    key = rKPs[eid].key;
    return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
    return nextNode;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
    nextNode = pid;
    return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
    return pf.read(pid, buffer);
}    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
    return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
    return numEntries;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
    // if full, err out
    if (numEntries == maxEntries) {
        return RC_NODE_FULL;
    }
    // find the correct spot and make a gap.
    int i = 0;
    while(i < numEntries) {
        if(kPPs[i].key >= key){
            memmove(kPPs + i + 1 , kPPs + i, sizeKPP * (numEntries - i));
            break;
        }
        i++;
    }
    
    // add kPP
    kPPs[i] = kPP(pid, key);
    
    //increment count
    numEntries++;
    
    return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
    if (numEntries < 2){
        return RC_TOO_FEW_FOR_INSERT_AND_SPLIT;
    }


    const int split = (numEntries - 1) / 2;
    
    // determine where new node will be inserted
    if(kPPs[split].key <= key){
        if(key < kPPs[split + 1].key)
        {
            midKey = key;
            sibling.minNode =  pid;
            sibling.numEntries = numEntries - (split + 1);
            numEntries = split + 1;
            memcpy(sibling.kPPs, kPPs + split + 1, sizeKPP * sibling.numEntries);
        }
        else{
            midKey = kPPs[split + 1].key;
            sibling.minNode = kPPs[split + 1].pointer;
            sibling.numEntries = numEntries - (split + 2);
            numEntries = split + 1;
            memcpy(sibling.kPPs, kPPs + split + 2, sizeKPP * sibling.numEntries);
            sibling.insert(key, pid);
        }
    }
    else{
        midKey = kPPs[split].key;
        sibling.minNode = kPPs[split].pointer;
        sibling.numEntries = numEntries - (split + 1);
        numEntries = split;
        memcpy(sibling.kPPs, kPPs + split + 1, sizeKPP * sibling.numEntries);
        insert(key, pid);
    }
    
    return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
    if(searchKey < kPPs[0].key){
        pid = minNode;
        return 0;
    }
    
    for(int i = 1; i <numEntries; i++ ){
        if (kPPs[i-1].key <= searchKey && searchKey < kPPs[i].key) {
            pid = kPPs[i-1].pointer;
            return 0;
        }
    }
    
    pid = kPPs[numEntries-1].pointer;
    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
    minNode = pid1;
    kPPs[0] = kPP(key, pid2);
    numEntries = 1;
    return 0;
}
